package lib.checkrep;

public abstract class TreeCheck {
  
  /**
   * Checks whether it's a tree rooted NOT NECESSARILY at 0.
   *
   * Works in N^2. TODO(irvan): optimize this
   * 
   * @param parent parent[i] is node i's parent, or -1 if it's root.
   * @return
   */
  public static boolean IsTree(int[] parent) {
    int n = parent.length;
    
    // assert exactly one root
    int roots = 0;
    for (int i = 0; i < parent.length; ++i) {
      assert parent[i] >= -1 && parent[i] < n;
      if (parent[i] == -1) ++roots;
    }
    
    if (roots != 1) {
      System.out.println("NOT TREE: roots = " + roots);
      return false;
    }
    
    // assert all nodes ends at root
    // N^2
    for (int i = 0; i < n; ++i) {
      int z = i;
      for (int j = 0; j < n+4; ++j) {
        if (z == -1) break;
        z = parent[z];
      }
      if (z != -1) {
        System.out.println("NOT TREE: Loop detected");
        return false;  // Loop detected
      }
    }
    
    return true;
  }
}
